package com.example.algorithm.backtracing;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给定一个不含重复数字的数组 nums(leetcode46) ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 给定一个含重复数字的数组 nums(leetcode47) ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * <p>
 * leetcode46
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * <p>
 * 示例 2：
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * <p>
 * 示例 3：
 * 输入：nums = [1]
 * 输出：[[1]]
 * <p>
 * leetcode47
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],[1,2,1],[2,1,1]]
 * <p>
 * 示例 2：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * <p>
 * <p>
 * 提示：
 * 1 <= nums.length <= 6
 * -10 <= nums[i] <= 10
 * nums 中的所有整数 互不相同
 */
public class Leetcode46And47_Permute {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {2, 2, 1, 1};
//        List<List<Integer>> res = new Solution().permute(nums1);
//        System.out.println(res.size());
//        res.forEach(r -> {
//            r.forEach(e -> System.out.print(e + ", "));
//            System.out.println();
//        });


        List<List<Integer>> res2 = new Solution().permuteUnique(nums2);
        res2.forEach(r -> {
            r.forEach(e -> System.out.print(e + ", "));
            System.out.println();
        });

    }

    static class Solution {

        /**
         * 有重复的元素全排列
         *
         * @param nums
         * @return
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> ress = new ArrayList<>();
            Deque<Integer> singleRes = new ArrayDeque<>();
            boolean[] visited = new boolean[nums.length];
            Arrays.sort(nums); // 为了方便剪枝
            backTraceUnique(ress, nums, singleRes, 0, visited);

            // 去重后返回
            return ress;
        }

        /**
         * 没有重复元素的全排列
         *
         * @param nums
         * @return
         */
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> ress = new ArrayList<>();
            Deque<Integer> singleRes = new ArrayDeque<>();
            boolean[] visited = new boolean[nums.length];
            backTrace(ress, nums, singleRes, 0, visited);

            return ress;
        }

        private void backTraceUnique(List<List<Integer>> ress, int[] nums, Deque<Integer> path, int depth, boolean[] visited) {
            if (depth == nums.length) { // 所有数字都加入到了一个singleRes中就将单个结果集加入到总的结果集并退出递归
                // 注意不能直接添加path,因为整个递归完毕后被置空了[],如果只添加引用则每个子结果集都会是空
                ress.add(new ArrayList<>(path)); // 相当于对当前的状态做了一个拷贝,如果不做拷贝那么最终所有的结果集都是空
                return;
            }

            for (int i = 0; i < nums.length; i++) {

                if (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) // 对相邻两个元素相同时并且刚刚访问过前一个的情况进行剪枝
                    continue;

                if (!visited[i]) { // 某个下元素未被访问过才能加入到单个的结果集合(single)中
                    path.addLast(nums[i]);
                    visited[i] = true;
                    backTraceUnique(ress, nums, path, depth + 1, visited);
                    path.removeLast(); // 恢复之前的状态
                    visited[i] = false;
                }
            }
        }

        /**
         * dfs回溯求解结果集
         *
         * @param ress
         * @param nums
         * @param path    暂存递归访问的路径(栈结构)
         * @param depth   递归的深度(层数)
         * @param visited 数组元素是否被访问过
         */
        private void backTrace(List<List<Integer>> ress, int[] nums, Deque<Integer> path, int depth, boolean[] visited) {
            if (depth == nums.length) { // 当递归深度 = 数组长度,即是数组的每个元素都已经放入了路径栈 path 中
                // 注意不能直接添加path,因为整个递归完毕后该list被置空了[]
                ress.add(new ArrayList<>(path)); // 相当于对当前的状态做了一个拷贝,如果不做拷贝那么最终所有的结果集都会是空
                return;
            }

            for (int i = 0; i < nums.length; i++) {
                if (!visited[i]) { // 某个下元素未被访问过才能加入到单个的结果集合中
                    path.addLast(nums[i]);
                    visited[i] = true;
                    backTrace(ress, nums, path, depth + 1, visited);
                    path.removeLast(); // 恢复之前的状态
                    visited[i] = false;
                }
            }
        }
    }
}
